//
// Created by LH on 2017/9/7.
//利用邻接表储存图，然后从start开始搜索，与start直接连接的都进行松弛，然后入队，直到队列为空
#include <iostream>
using namespace std;

int map[50][3];
int book[50];
int queue[50];
int first[50], nxt[50];
int head = 0, tail = 0;
int n, m, start;
int dis[50];
int cnt[50];
int main()
{
    cin >> n >> m >> start;
    for (int t_init=0;t_init<=n;t_init++)
    {
        dis[t_init] = 1e9;
        first[t_init] = -1;
    }
    for (int t_ipt=1;t_ipt<=m;t_ipt++)
    {
        int t1, t2, t3;
        cin >> t1 >> t2 >> t3;
        map[t_ipt][0] = t1;
        map[t_ipt][1] = t2;
        map[t_ipt][2] = t3;
        nxt[t_ipt] = first[t1];
        first[t1] = t_ipt;
    }
    book[start]=1;
    queue[tail] = start;
    tail++;
    dis[start] = 0;
    while (head<tail)
    {
        int index=first[queue[head]];
        while (index!=-1)
        {
            if (dis[map[index][0]] + map[index][2] < dis[map[index][1]])
            {
                dis[map[index][1]] = dis[map[index][0]] + map[index][2];    //松弛操作
                if (!book[map[index][1]])
                {
                    queue[tail] = map[index][1];
                    tail++;
                    book[map[index][1]] = 1;
                    cnt[map[index][1]]++;
                    if (cnt[map[index][1]]>n)   //若一个节点入队超过n，则说明此图含有负权回路
                    {
                        cout << "存在负权回路!";
                        return 0;
                    }
                }
            }
            index = nxt[index];
        }
        book[queue[head]] = 0;
        head++;
    }

    for (int t_pnt = 1; t_pnt <= n; t_pnt++)
    {
        cout << dis[t_pnt] << " ";
    }
    return 0;
}